10611. Играющий ребенок

Элементы неубывающей последовательности n чисел представляет собой высоты людей. Помогите Лучу - шимпанзе найти человека, имеющего наибольшую высоту, меньшую чем у Лучу и человека с наименьшей высотой, большей чем у Лучу.

Вход. Первая строка содержит значение n (1 £ n £ 50000). Следующая строка содержит неубывающую последовательность из n чисел. Далее следует количество запросов q (1 £ q £ 25000). Каждый запрос представляет собой высоту Лучу.

Выход. Для каждой заданной высоты Лучу вывести два числа: первое число должно содержать наибольшую высоту человека, меньшую чем у Лучу, второе число – наименьшую высоту человека, большую чем у Лучу.

Пример входа

4
1 4 5 7
4

4 6 8 10

Пример выхода

1 5
5 7
7 X

7 X

РЕШЕНИЕ

бинарный поиск

Анализ алгоритма

Читаем последовательность из n чисел в массив m. При этом удаляем повторяющиеся элементы. Для каждого тестируемого значения i бинарным поиском ищем позицию, на которую необходимо его вставить с сохранением условия неубываемости. При этом будем пользоваться функцией upper_bound, которая ищет номер вставляемой позиции по верхней границе. Остается проверить, содержит ли входной массив значение i, и в зависимости от этого вывести искомые значения.

Пример

Число 4 лежит между 1 и 5, число 6 – между 5 и 7. Для 8 и 10 нижней границей будет 7, а верхней границы нет.

Реализация алгоритма

Читаем числа в массив int m[50000]. В нулевую ячейку массива запишем 0, в последнюю (индекс которой будет известен после прочтения всех чисел массива) занесем максимально возможное число. Если текущее число равно предыдущему, то пропускаем его. Если не равно, то заносим в массив. Переменной n присвоим индекс последней ячейки.

scanf("%d",&n);

m[0] = 0; i = 1;

while(n--)

{

scanf("%d",&m[i]);

if (m[i] != m[i-1]) i++;

}

n = i; m[n] = 0x7FFFFFFF;

Для каждого тестируемого значения i находим позицию pos по верхней границе, куда его следует вставить при помощи функции upper_bound. Далее следует обработать два случая: если значение i уже есть в массиве m (m[pos – 1] = i), то выводить m[pos – 2] и m[pos]. Иначе следует вывести m[pos – 1] и m[pos].

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&i);

pos = upper_bound(m,m+n,i) - m;

if (m[pos-1] == i) { out(m[pos-2]); printf(" "); out(m[pos]); }

else { out(m[pos-1]); printf(" "); out(m[pos]); };

printf("\n");

}

Функция out(n) выводит число n, если оно не равно 0 или 0x7FFFFFFF. Иначе выводится символ “X”.

void out(int i)

{

if (!i || i == 0x7FFFFFFF) printf("X");

else printf("%d",i);

}